{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Elimination Game"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #recursion #math"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #递归 #数学"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: lastRemaining"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #消除游戏"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>列表 <code>arr</code> 由在范围 <code>[1, n]</code> 中的所有整数组成，并按严格递增排序。请你对 <code>arr</code> 应用下述算法：</p>\n",
    "\n",
    "<div class=\"original__bRMd\">\n",
    "<div>\n",
    "<ul>\n",
    "\t<li>从左到右，删除第一个数字，然后每隔一个数字删除一个，直到到达列表末尾。</li>\n",
    "\t<li>重复上面的步骤，但这次是从右到左。也就是，删除最右侧的数字，然后剩下的数字每隔一个删除一个。</li>\n",
    "\t<li>不断重复这两步，从左到右和从右到左交替进行，直到只剩下一个数字。</li>\n",
    "</ul>\n",
    "\n",
    "<p>给你整数 <code>n</code> ，返回 <code>arr</code> 最后剩下的数字。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 9\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>\n",
    "arr = [<strong><em>1</em></strong>, 2, <em><strong>3</strong></em>, 4, <em><strong>5</strong></em>, 6, <em><strong>7</strong></em>, 8, <em><strong>9</strong></em>]\n",
    "arr = [2, <em><strong>4</strong></em>, 6, <em><strong>8</strong></em>]\n",
    "arr = [<em><strong>2</strong></em>, 6]\n",
    "arr = [6]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 1\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>9</sup></code></li>\n",
    "</ul>\n",
    "</div>\n",
    "</div>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [elimination-game](https://leetcode.cn/problems/elimination-game/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [elimination-game](https://leetcode.cn/problems/elimination-game/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['9', '1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        else:\n",
    "            return (n // 2 + 1 - self.lastRemaining(n // 2)) * 2 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        k, cnt, step = 0, n, 1\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:  # 正向\n",
    "                a1 += step\n",
    "            else:  # 反向\n",
    "                if cnt % 2:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "        return a1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        return self.func(n, True)\n",
    "\n",
    "    def func(self, n, isLeft):\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        # 奇数\n",
    "        if isLeft:\n",
    "            return 2 * self.func(n // 2, not isLeft)\n",
    "        if n % 2 == 1:\n",
    "            return 2 * self.func(n // 2, not isLeft)\n",
    "        return 2 * self.func(n // 2, not isLeft) - 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "        \n",
    "        while n > 1:\n",
    "            # 从左边开始移除 or（从右边开始移除，数列总数为奇数）\n",
    "            if left or n % 2 != 0:\n",
    "                head += step\n",
    "            \n",
    "            step <<= 1 # 步长 * 2\n",
    "            n >>= 1 # 总数 / 2\n",
    "            left = not left #取反移除方向\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "        while n>1:\n",
    "            if left or n%2:\n",
    "                head+=step\n",
    "            step*=2\n",
    "            left=not left\n",
    "            n>>=1\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        k, cnt, step = 0, n, 1\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:  # 正向\n",
    "                a1 += step\n",
    "            else:  # 反向\n",
    "                if cnt % 2:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "        return a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        start, cnt, step = 1, n, 1\n",
    "        drct = 0\n",
    "        while cnt > 1:\n",
    "            if drct % 2 == 0:\n",
    "                start += step\n",
    "            else:\n",
    "                if cnt % 2:\n",
    "                    start += step\n",
    "            drct += 1\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "        return start\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        k = 1  # 删除次数, 次数为奇数则为正向删除, 偶数为反向删除\n",
    "        cnt = n  # 元素总数, 有: cnt(k+1) = cnt(k) // 2\n",
    "        step = 1  # 每轮所剩等差数列的公差, 有: step(k+1) = step(k) * 2\n",
    "        while cnt != 1:\n",
    "            # 正向删除\n",
    "            if k % 2 == 1:\n",
    "                a1 += step\n",
    "            # 反向删除\n",
    "            else:\n",
    "                if cnt % 2 == 1:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt //= 2\n",
    "            step *= 2\n",
    "        return a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        result = 1\n",
    "        current = n\n",
    "        left_to_rigt = True\n",
    "        action1 = lambda x: x*2\n",
    "        action2 = lambda x: x*2 - 1\n",
    "        action_list = []\n",
    "\n",
    "        while current != 1:\n",
    "            if left_to_rigt:\n",
    "                current = current // 2\n",
    "                action_list.append(action1)\n",
    "                left_to_rigt = False\n",
    "            else:\n",
    "                left_to_rigt = True\n",
    "                if current % 2 == 0:\n",
    "                    current = current // 2\n",
    "                    action_list.append(action2)\n",
    "                else:\n",
    "                    current = current // 2\n",
    "                    action_list.append(action1)\n",
    "        for item in action_list[::-1]:\n",
    "            result = item(result) \n",
    "        \n",
    "        return result\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head = 1\n",
    "        k, cnt, step = 0, n, 1\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:  # 正向\n",
    "                head += step\n",
    "            else:  # 反向\n",
    "                if cnt % 2 == 1:\n",
    "                    head += step\n",
    "            k += 1\n",
    "            cnt //= 2\n",
    "            step *= 2\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        b=bin(n)[2:]\n",
    "        l=len(b)\n",
    "        result=pow(2,l-1)\n",
    "        for i in range(l-2,-1,-2):\n",
    "            c=b[i]\n",
    "            if c=='0':\n",
    "                result-=pow(2,l-1-i)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "        \n",
    "        while n > 1:\n",
    "            # 从左边开始移除 or（从右边开始移除，数列总数为奇数）\n",
    "            if left or n % 2 != 0:\n",
    "                head += step\n",
    "            \n",
    "            step <<= 1 # 步长 * 2\n",
    "            n >>= 1 # 总数 / 2\n",
    "            left = not left #取反移除方向\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        k, cnt, step = 0, n, 1\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:\n",
    "                a1 += step\n",
    "            else:\n",
    "                if cnt % 2:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "        return a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        # 先看看暴力  -- 直接超时\n",
    "        # arr = [x for x in range(1, n+1)]\n",
    "        # print(arr)\n",
    "        # while len(arr) > 2:\n",
    "        #     tm = []\n",
    "        #     n = len(arr)\n",
    "        #     i = 0\n",
    "        #     flag = 1\n",
    "        #     while i < n-1:\n",
    "        #         if flag == 1:\n",
    "        #             continue\n",
    "        #         else:\n",
    "        #             tm.append(arr[i])\n",
    "        #         i += 1\n",
    "        #         flag *= -1\n",
    "        #     print(tm)\n",
    "        #     arr = tm[::-1]\n",
    "        # print(arr)\n",
    "\n",
    "        # 网友的模拟\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "        while n > 1:\n",
    "            if left or n % 2 != 0:\n",
    "                head += step\n",
    "            step <<= 1\n",
    "            n >>= 1\n",
    "            left = not left\n",
    "        return head\n",
    "            \n",
    "            \n",
    "                 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        ans = 1         # 最左边的数\n",
    "        step = 1        # 数组里每个数之间的差\n",
    "        left = True     # 是否从左边开始移动\n",
    "        while n > 1:\n",
    "            # 最左边会变的情况: 1. 从左边开始移除 2. 从右边开始移除, 数组剩奇数个\n",
    "            if left or n % 2:\n",
    "                ans += step\n",
    "            n = n // 2          # 剩多少个数\n",
    "            step *= 2           # 数组之间的差值\n",
    "            left = not left     # 换方向\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        result = 1\n",
    "        current = n\n",
    "        left_to_rigt = True\n",
    "        actions = {'multi2': lambda x: x*2, 'multi2mins1': lambda x: x*2 - 1 }\n",
    "        action_list = []\n",
    "\n",
    "        while current != 1:\n",
    "            if left_to_rigt:\n",
    "                current = current // 2\n",
    "                action_list.append('multi2')\n",
    "                left_to_rigt = False\n",
    "            else:\n",
    "                left_to_rigt = True\n",
    "                if current % 2 == 0:\n",
    "                    current = current // 2\n",
    "                    action_list.append('multi2mins1')\n",
    "                else:\n",
    "                    current = current // 2\n",
    "                    action_list.append('multi2')\n",
    "        for item in action_list[::-1]:\n",
    "            result = actions[item](result) \n",
    "        \n",
    "        return result\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "        \n",
    "        while n > 1:\n",
    "            # 从左边开始移除 or（从右边开始移除，数列总数为奇数）\n",
    "            if left or n % 2 != 0:\n",
    "                head += step\n",
    "            \n",
    "            step <<= 1 # 步长 * 2\n",
    "            n >>= 1 # 总数 / 2\n",
    "            left = not left #取反移除方向\n",
    "\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        if n % 2 == 1:\n",
    "            return self.lastRemaining(n - 1)\n",
    "        else:\n",
    "            return n + 2 - 2 * self.lastRemaining(n // 2)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mem=[]#0:/2,1:+1/2\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        #ph1\n",
    "        while 1:\n",
    "            if n==1:\n",
    "                break\n",
    "            n=n//2\n",
    "            #ph2\n",
    "            self.mem.append(1)\n",
    "            if n==1:\n",
    "                break\n",
    "            self.mem.append(n&1)\n",
    "            n=n//2\n",
    "        ret = 1\n",
    "        for i in self.mem[::-1]:\n",
    "            if i==0:\n",
    "                ret = ret*2-1\n",
    "            else:\n",
    "                ret = ret*2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        k, cnt, step = 0, n, 1\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:  # 正向\n",
    "                a1 += step\n",
    "            else:  # 反向\n",
    "                if cnt % 2:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "        return a1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "\n",
    "        # 1,2,3,4,5,6,7,8,9,10,11,12,13,14\n",
    "        # 2,4,6,8,10,12,14\n",
    "        # 4,8,12\n",
    "        # 8\n",
    "\n",
    "        # 1. remove all odd number\n",
    "        # 2. if n % 2 == 0 remove all even number else remove all odd number\n",
    "        # repeat 1 & 2\n",
    "\n",
    "        s = 1\n",
    "        step = 1\n",
    "        \n",
    "        while n != 1:\n",
    "\n",
    "            n = n // 2\n",
    "            s = s + step\n",
    "            step *= 2\n",
    "        \n",
    "            if n == 1:\n",
    "                break\n",
    "            \n",
    "            if n % 2 == 1:\n",
    "                n = n // 2\n",
    "                s = s + step\n",
    "                step *= 2\n",
    "            else:\n",
    "                n = n // 2\n",
    "                step *= 2\n",
    "\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        elif n%2==1:\n",
    "            return self.lastRemaining(n-1)\n",
    "        else:\n",
    "            return 2+n-2*self.lastRemaining(n//2)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        # arr = [i for i in range(1, n + 1)]\n",
    "        # while len(arr) > 1:\n",
    "        #     arr1 = []\n",
    "        #     for i in range(1,len(arr),2):\n",
    "        #         arr1.append(arr[i])\n",
    "        #     arr = arr1[::-1]\n",
    "\n",
    "        # return arr[0]\n",
    "\n",
    "        # 等差数列首位数\n",
    "        first = 1\n",
    "        # 等差数列差值\n",
    "        gap = 1\n",
    "        # 等差数列个数\n",
    "        cnt = n\n",
    "        # 删除方向，0-从左到右，1表示从右往左\n",
    "        order = 0\n",
    "\n",
    "        while cnt > 1:\n",
    "            if not order or cnt % 2:\n",
    "                first += gap\n",
    "            \n",
    "            cnt //= 2\n",
    "            gap *= 2\n",
    "            order = 1 - order\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        # nums = [(i + 1) for i in range(n)]\n",
    "        # cnt = 1\n",
    "        # while len(nums) > 1:\n",
    "        #     # print(nums)\n",
    "        #     if cnt % 2 == 0 and len(nums) % 2 == 0:\n",
    "        #         nums = nums[: : 2]\n",
    "        #     else:\n",
    "        #         nums = nums[1: : 2]\n",
    "        #     cnt += 1\n",
    "        # return nums[0]\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "        while n > 1:\n",
    "            if n % 2 == 1 or left == True:\n",
    "                head += step\n",
    "            step *= 2\n",
    "            left = not left\n",
    "            n //= 2\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        \"\"\"\n",
    "        模拟：暴力法肯定是能做的\n",
    "        1，2，3，4，5，6, 7, 8, 9\n",
    "        2，4，6, 8\n",
    "        2, 6\n",
    "        6\n",
    "        观察:\n",
    "        - 每次留下数字的开头\n",
    "            - 正向：start+step\n",
    "            - 反向：\n",
    "                - 奇数个留下 start+step\n",
    "                - 偶数个留下 start\n",
    "        \"\"\"\n",
    "\n",
    "        step = 1\n",
    "        start = 1\n",
    "        cnt = 1\n",
    "        while n>1:\n",
    "            if cnt % 2 == 1:\n",
    "                # 正向\n",
    "                start = start + step\n",
    "            else:\n",
    "                if n % 2 == 0:\n",
    "                    pass\n",
    "                else:\n",
    "                    start = start + step\n",
    "            n //= 2\n",
    "            cnt += 1\n",
    "            step *= 2\n",
    "        \n",
    "        return start\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        result = 1\n",
    "        current = n\n",
    "        left_to_rigt = True\n",
    "        actions = {'multi2': lambda x: x*2, 'multi2mins1': lambda x: x*2 - 1 }\n",
    "        action_list = []\n",
    "\n",
    "        while current != 1:\n",
    "            if left_to_rigt:\n",
    "                current = current // 2\n",
    "                action_list.append('multi2')\n",
    "                left_to_rigt = False\n",
    "            else:\n",
    "                left_to_rigt = True\n",
    "                if current % 2 == 0:\n",
    "                    current = current // 2\n",
    "                    action_list.append('multi2mins1')\n",
    "                else:\n",
    "                    current = current // 2\n",
    "                    action_list.append('multi2')\n",
    "        for item in action_list[::-1]:\n",
    "            result = actions[item](result) \n",
    "        \n",
    "        return result\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        row, cnt, step = 0, n, 1\n",
    "        while cnt > 1:\n",
    "            if row % 2 == 0:\n",
    "                a1 += step\n",
    "            else:\n",
    "                if cnt % 2 == 1:\n",
    "                    a1 += step\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "            row += 1\n",
    "        return a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        num=0\n",
    "        head=1\n",
    "        while(n!=1):\n",
    "            if n%2==1:\n",
    "                head+=+2**num\n",
    "                n=(n-1)//2\n",
    "                num+=1\n",
    "                continue\n",
    "            if n%2==0:\n",
    "                if num%2==0:\n",
    "                    head+=2**num\n",
    "                n=n//2\n",
    "                num+=1\n",
    "                continue\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "        \n",
    "        while n > 1:\n",
    "            # 从左边开始移除 or（从右边开始移除，数列总数为奇数）\n",
    "            if left or n % 2 != 0:\n",
    "                head += step\n",
    "            \n",
    "            step <<= 1 # 步长 * 2\n",
    "            n >>= 1 # 总数 / 2\n",
    "            left = not left #取反移除方向\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        def help(l, r, L2R):\n",
    "            if l == r:\n",
    "                return l\n",
    "            t = help(1, (r - l + 1) // 2, L2R ^ 1) * 2\n",
    "            return t if L2R or (r - l + 1) % 2 == 1 else t - 1\n",
    "        return help(1, n, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head=1\n",
    "        direct=True\n",
    "        step=1\n",
    "        while n>1:\n",
    "            if n%2==1 or n%2==0 and direct:\n",
    "                head+=step\n",
    "            n//=2\n",
    "            step*=2\n",
    "            direct=not direct\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        #n=int(input())\n",
    "        head,left,step=1,True,1\n",
    "        while n>1:\n",
    "            if left or  n%2==1:\n",
    "                head+=step\n",
    "            step <<=1\n",
    "            n>>=1\n",
    "            left=not left\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        start=1\n",
    "        gap=1\n",
    "        direct=0\n",
    "        num=n \n",
    "        while(num!=1):\n",
    "            half=math.ceil(num/2)\n",
    "            if direct==0:\n",
    "                new_start=start+gap \n",
    "\n",
    "            else:\n",
    "                if half*2==num:\n",
    "                    new_start=start\n",
    "                else:\n",
    "                    new_start=start+gap\n",
    "\n",
    "\n",
    "            gap*=2\n",
    "            start=new_start\n",
    "            direct=1-direct\n",
    "            num-=half\n",
    "\n",
    "        return start"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        return self.digui(1, 1, n, 1)\n",
    "\n",
    "    def digui(self, f_num, step, cnt, dire):\n",
    "        # print(f_num, step, cnt)\n",
    "        if cnt == 1:\n",
    "            return f_num\n",
    "        if dire == 1:\n",
    "            cnt //= 2\n",
    "            f_num += step\n",
    "            step *= 2\n",
    "            return self.digui(f_num, step, cnt, -1)\n",
    "        else:\n",
    "            if cnt % 2 == 1:\n",
    "                f_num += step\n",
    "            step *= 2\n",
    "            cnt //= 2\n",
    "            return self.digui(f_num, step, cnt, 1)\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        b = 2\n",
    "        e = n\n",
    "        if n % 2 == 1:\n",
    "            e = n - 1\n",
    "        k = 2\n",
    "        g = 'r'\n",
    "        kk = n // 2\n",
    "        while b < e:\n",
    "            if g == 'r':\n",
    "                if kk % 2 == 1:\n",
    "                    b += k\n",
    "                    e -= k\n",
    "                else:\n",
    "                    e -= k\n",
    "                g = 'l'\n",
    "            else:\n",
    "                if kk % 2 == 1:\n",
    "                    b += k\n",
    "                    e -= k\n",
    "                else:\n",
    "                    b += k\n",
    "                g = 'r'\n",
    "            k *= 2\n",
    "            kk //= 2\n",
    "        return e"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        left=True\n",
    "        head=1\n",
    "        step=1\n",
    "        while n!=1:\n",
    "            if left:\n",
    "                head+=step\n",
    "                left=False\n",
    "            else:\n",
    "                if n%2==1:\n",
    "                    head+=step\n",
    "                left=True\n",
    "            step*=2\n",
    "            n=n//2\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        time = 1#轮数\n",
    "        first = 1#删除后首项\n",
    "        while n!=1:\n",
    "            if time%2 == 1:#轮数奇数时\n",
    "                first += 2**(time-1)\n",
    "            else:#轮数偶数时\n",
    "                if n%2 == 1:#且n奇数时\n",
    "                    first += 2**(time-1)\n",
    "            n = n//2\n",
    "            time += 1\n",
    "        return first"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        k, cnt, step = 0, n, 1\n",
    "\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:\n",
    "                a1 += step\n",
    "            else:\n",
    "                if cnt % 2:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "        return a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        k, cnt, step = 0, n, 1\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:  # 正向\n",
    "                a1 += step\n",
    "            else:  # 反向\n",
    "                if cnt % 2:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "        return a1\n",
    "        '''\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2 or n == 3:\n",
    "            return 2\n",
    "        if n % 2 == 0:\n",
    "            return n-2\n",
    "        else:\n",
    "            return n-3\n",
    "        '''\n",
    "        '''\n",
    "        nlist = []\n",
    "        for i in range(1,n+1):\n",
    "            nlist.append(i)\n",
    "        going = 1\n",
    "        #print(nlist)\n",
    "        while len(nlist) > 1:\n",
    "            #print(nlist)\n",
    "            if going == 1:\n",
    "                #pops = []\n",
    "                for i in range(len(nlist)-1,-1,-1):\n",
    "                    if i % 2 == 0:\n",
    "                        #pops.append(i)\n",
    "                        nlist.pop(i)\n",
    "                #for pop in range(len(pops)-1,-1,-1):\n",
    "                    #nlist.pop(pops[pop])\n",
    "                #print(pops)\n",
    "                going = 0\n",
    "            elif going == 0:\n",
    "                #pops = []\n",
    "                thisl = len(nlist)\n",
    "                for i in range(len(nlist)-1,-1,-1):\n",
    "                    if i % 2 == 1 and thisl % 2 == 0:\n",
    "                        #pops.append(i)\n",
    "                        nlist.pop(i)\n",
    "                    elif i % 2 == 0 and thisl % 2 == 1:\n",
    "                        #pops.append(i)\n",
    "                        nlist.pop(i)\n",
    "                #for pop in range(len(pops)-1,-1,-1):\n",
    "                    #nlist.pop(pops[pop])\n",
    "                #print(pops)\n",
    "                going = 1\n",
    "        return nlist[0]\n",
    "'''\n",
    "'''\n",
    "[1] 1\n",
    "[1,2] 2\n",
    "[1,2,3] 2\n",
    "[1,2,3,4] 2\n",
    "[1,2,3,4,5] 2\n",
    "[1,2,3,4,5,6] 4\n",
    "[1,2,3,4,5,6,7] 4\n",
    "[1,2,3,4,5,6,7,8] 6\n",
    "[1,2,3,4,5,6,7,8,9] 6\n",
    "[1,2,3,4,5,6,7,8,9,10] 8\n",
    "[1,2,3,4,5,6,7,8,9,10,11] 8\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        ans = 2 * (n // 2 + 1 - self.lastRemaining(n // 2))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        first = True\n",
    "        last = False\n",
    "        head = 1\n",
    "        tail = n\n",
    "        step = 1\n",
    "\n",
    "        while head!=tail:\n",
    "\n",
    "            if (tail-head)/step%2 == 0:\n",
    "                head += step\n",
    "                tail -= step\n",
    "                step*=2\n",
    "\n",
    "            else:\n",
    "                if first:\n",
    "                    head+=step\n",
    "                    step*=2\n",
    "                elif last:\n",
    "                    tail-=step\n",
    "                    step*=2\n",
    "                \n",
    "\n",
    "            first = not first\n",
    "            last = not last\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        r = range(1,n+1)\n",
    "        \n",
    "        flag = True\n",
    "        while len(r) !=1:\n",
    "            if flag == True:\n",
    "                r = r[1::2]\n",
    "            else:\n",
    "                r = r[len(r)%2::2]\n",
    "            flag = not flag\n",
    "        a = r[0]\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        cnt, step, k = n, 1, 0\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:\n",
    "                a1 += step\n",
    "            else:\n",
    "                if cnt % 2 != 0:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            step <<= 1\n",
    "            cnt >>= 1\n",
    "        return a1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n==1:\n",
    "            return 1\n",
    "        return 2*(n//2+1-self.lastRemaining(n//2))\n",
    "        \n",
    "        \n",
    "        \n",
    "        # if n==1:\n",
    "        #     return 1\n",
    "        # res=list(range(1,n+1))\n",
    "        # while 1:\n",
    "        #     ans=[]\n",
    "        #     for i in res[1::2]:\n",
    "        #         ans.append(i)\n",
    "        #     if len(ans)==1:\n",
    "        #         return ans[0]\n",
    "        #     ans.reverse()\n",
    "        #     res=ans.copy()\n",
    "                \n",
    "                \n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        s = [1, n, 1]\n",
    "\n",
    "        for i in range(1, 1000):\n",
    "\n",
    "            if s[0] == s[1]:\n",
    "                return s[0]\n",
    "\n",
    "            if i % 2 == 1:\n",
    "                length = ((s[1] - s[0])/s[2]) + 1\n",
    "                if length % 2 == 1:\n",
    "                    start = s[0] + s[2]\n",
    "                    end = s[1] - s[2]\n",
    "                    gap = s[2]*2\n",
    "                    s = [start,end,gap]\n",
    "                else:\n",
    "                    start = s[0] + s[2]\n",
    "                    end = s[1]\n",
    "                    gap = s[2]*2\n",
    "                    s = [start,end,gap]\n",
    "            else:\n",
    "                length = ((s[1] - s[0])/s[2]) + 1\n",
    "                if length % 2 == 1:\n",
    "                    start = s[0] + s[2]\n",
    "                    end = s[1] - s[2]\n",
    "                    gap = s[2]*2\n",
    "                    s = [start,end,gap]\n",
    "                else:\n",
    "                    start = s[0]\n",
    "                    end = s[1] - s[2]\n",
    "                    gap = s[2]*2\n",
    "                    s = [start,end,gap]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1\n",
    "        k, cnt, step = 0, n, 1\n",
    "        while cnt > 1:\n",
    "            if k % 2 == 0:  # 正向\n",
    "                a1 += step\n",
    "            else:  # 反向\n",
    "                if cnt % 2:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt >>= 1\n",
    "            step <<= 1\n",
    "        return a1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        def help(l, r, L2R):\n",
    "            if l == r:\n",
    "                return l\n",
    "            if L2R or (r - l + 1) % 2 == 1:\n",
    "                return help(1, (r - l + 1) // 2, L2R ^ 1) * 2\n",
    "            return help(1, (r - l + 1) // 2, L2R ^ 1) * 2 - 1\n",
    "        return help(1, n, 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        \n",
    "        result = 1\n",
    "        current = n\n",
    "        left_to_rigt = True\n",
    "        actions = {'multi2': lambda x: x*2, 'multi2mins1': lambda x: x*2 - 1 }\n",
    "        action_list = []\n",
    "\n",
    "        while current != 1:\n",
    "            if left_to_rigt:\n",
    "                current = current // 2\n",
    "                action_list.append('multi2')\n",
    "                left_to_rigt = False\n",
    "            else:\n",
    "                left_to_rigt = True\n",
    "                if current % 2 == 0:\n",
    "                    current = current // 2\n",
    "                    action_list.append('multi2mins1')\n",
    "                else:\n",
    "                    current = current // 2\n",
    "                    action_list.append('multi2')\n",
    "        for item in action_list[::-1]:\n",
    "            result = actions[item](result) \n",
    "        \n",
    "        return result\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        remain = n\n",
    "        flag = True # from left to right is true\n",
    "        res = 1\n",
    "        step = 1\n",
    "        while remain > 1:\n",
    "            if flag or remain % 2 == 1:\n",
    "                res += step\n",
    "            flag = not flag\n",
    "            step *= 2\n",
    "            remain //= 2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head=1\n",
    "        step=1\n",
    "        left=True\n",
    "        \n",
    "        while n>1:\n",
    "            if left or n%2==1:\n",
    "                head+=step\n",
    "            step*=2\n",
    "            n//=2\n",
    "            left=not left\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "      if n == 1:\n",
    "          return 1\n",
    "      minIterNum = int(log2(n))\n",
    "      former = [0, 1, 1, n]  # 迭代次数、最左侧元素、步长、迭代后剩余元素个数\n",
    "      cur = former\n",
    "      # 奇数次迭代首个元素肯定跳变，偶数次迭代首个元素是否跳变要看上次迭代后列表元素个数是否为奇数，若为奇数就跳变\n",
    "      for time in range(1, minIterNum + 1):\n",
    "          if time % 2 == 0:  # 偶数次迭代\n",
    "              if former[3] % 2 == 0:  # 上次迭代后列表元素个数为偶数\n",
    "                  cur = [time, former[1], 2 ** time, former[3] / 2]\n",
    "              else:  # 上次迭代后列表元素个数为奇数\n",
    "                  cur = [time, former[1] + former[2], 2 ** time, former[3] // 2]\n",
    "          else:  # 奇数次迭代\n",
    "              cur = [time, former[1] + former[2], 2 ** time, former[3] // 2]\n",
    "          former = cur\n",
    "      if cur[1] + cur[2] <= n:\n",
    "          if minIterNum % 2 != 0:\n",
    "              return cur[1] + cur[2]\n",
    "          else:\n",
    "              return cur[1]\n",
    "      return cur[1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        def lt390(n):\n",
    "            ops=[]\n",
    "            if n>1:\n",
    "                ops.append(-1)\n",
    "                n//=2\n",
    "            while n>1:\n",
    "                ops.append(n)\n",
    "                n//=2\n",
    "                ops.append(-1)\n",
    "            p=1\n",
    "            for i in range(len(ops)-1,-1,-1):\n",
    "                op=ops[i]\n",
    "                if op==-1:p=2*p\n",
    "                else:p=op+1-p\n",
    "            return p\n",
    "        return lt390(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        l=1\n",
    "        ll=1\n",
    "        left=True\n",
    "        while n>1:\n",
    "            if left or n%2==1:\n",
    "                l+=ll\n",
    "            ll*=2\n",
    "            n//=2\n",
    "            left=not left\n",
    "        return l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def lastRemaining(self, n: int) -> int:\n",
    "        # arr = [i for i in range(1, n + 1)]\n",
    "        # while len(arr) > 1:\n",
    "        #     arr1 = []\n",
    "        #     for i in range(1,len(arr),2):\n",
    "        #         arr1.append(arr[i])\n",
    "        #     arr = arr1[::-1]\n",
    "\n",
    "        # return arr[0]\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        elif n < 4:\n",
    "            return 2\n",
    "        subLen = n // 4\n",
    "        if (n // 2) % 2 == 0:   #最左端从2开始\n",
    "            subRet = self.lastRemaining(subLen) \n",
    "            return 2 + (subRet - 1) * 4\n",
    "        else:                   #最左端从4开始\n",
    "            subRet = self.lastRemaining(subLen) \n",
    "            return 4 + (subRet - 1) * 4\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "\n",
    "        while n > 1:\n",
    "            if left or n % 2 != 0:\n",
    "                head += step\n",
    "            \n",
    "            step <<= 1\n",
    "            n >>= 1\n",
    "            left = not left\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        a1 = 1  # 等差数列的第一个元素\n",
    "        k = 1  # 删除次数, 次数为奇数则为正向删除, 偶数为反向删除\n",
    "        cnt = n  # 元素总数, 有: cnt(k+1) = cnt(k) // 2\n",
    "        step = 1  # 每轮所剩等差数列的公差, 有: step(k+1) = step(k) * 2\n",
    "        while cnt != 1:\n",
    "            # 正向删除\n",
    "            if k % 2 == 1:\n",
    "                a1 += step\n",
    "            # 反向删除\n",
    "            else:\n",
    "                if cnt % 2 == 1:\n",
    "                    a1 += step\n",
    "            k += 1\n",
    "            cnt //= 2\n",
    "            step *= 2\n",
    "        return a1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        return 2 * (n // 2 + 1 - self.lastRemaining(n // 2))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        head = 1\n",
    "        step = 1\n",
    "        left = True\n",
    "        \n",
    "        while n > 1:\n",
    "            # 从左边开始移除 or（从右边开始移除，数列总数为奇数）\n",
    "            if left or n % 2 != 0:\n",
    "                head += step\n",
    "            \n",
    "            step <<= 1 # 步长 * 2\n",
    "            n >>= 1 # 总数 / 2\n",
    "            left = not left #取反移除方向\n",
    "\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        def foo(n):\n",
    "            if n == 1:\n",
    "                return 0\n",
    "            elif n & 1:\n",
    "                return foo(n - 1)\n",
    "            else:\n",
    "                return n - 1 - 2 * foo(n // 2)\n",
    "        return foo(n) + 1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.mem=[]#0:/2,1:+1/2\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        #ph1\n",
    "        while 1:\n",
    "            if n==1:\n",
    "                break\n",
    "            if n%2!=0:\n",
    "                n-=1\n",
    "            n=n//2\n",
    "            #ph2\n",
    "            self.mem.append(0)\n",
    "            if n==1:\n",
    "                break\n",
    "            if n%2==0:\n",
    "                self.mem.append(1)\n",
    "            else:\n",
    "                self.mem.append(0)\n",
    "            n=n//2\n",
    "        ret = 1\n",
    "        for i in self.mem[::-1]:\n",
    "            if i==1:\n",
    "                ret = ret*2-1\n",
    "            else:\n",
    "                ret = ret*2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        def dfs(left, right, rank, is_left):\n",
    "            s = (right - left) // rank + 1\n",
    "            if left == right:\n",
    "                return left\n",
    "            if right - left == rank:\n",
    "                return right if is_left else left\n",
    "            if is_left:\n",
    "                if s % 2:\n",
    "                    return dfs(left + rank, right - rank, rank * 2, not is_left)\n",
    "                else:\n",
    "                    return dfs(left + rank, right, rank * 2, not is_left)\n",
    "            else:\n",
    "                if s % 2:\n",
    "                    return dfs(left + rank, right - rank, rank * 2, not is_left)\n",
    "                else:\n",
    "                    return dfs(left, right - rank, rank * 2, not is_left)\n",
    "\n",
    "        return dfs(1, n, 1, True)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        @cache\n",
    "        def f(n):\n",
    "            if n == 1:\n",
    "                return 1\n",
    "            if n < 6:\n",
    "                return 2\n",
    "            if n % 2:\n",
    "                return f(n - 1)\n",
    "            return n - 2 * f( n // 2) + 2\n",
    "        \n",
    "        return f(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def lastRemaining(self, n: int) -> int:\n",
    "        def dfs(n,direct):\n",
    "            if n==1:\n",
    "                return 0\n",
    "            idx = dfs(n//2,-direct)\n",
    "            # print(n,direct,idx)\n",
    "            if direct>0 or (direct<0 and n%2==1):\n",
    "                return idx*2+1\n",
    "            else:\n",
    "                return idx*2\n",
    "        return dfs(n,1)+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def lastRemaining(self, n: int) -> int:\r\n",
    "        def f(n):\r\n",
    "            if n == 1:\r\n",
    "                return 1\r\n",
    "            return 2 * g(n // 2)\r\n",
    "        def g(n):\r\n",
    "            if n == 1:\r\n",
    "                return 1\r\n",
    "            if n % 2 == 1:\r\n",
    "                return 2 * f(n // 2)\r\n",
    "            else:\r\n",
    "                return 2 * f(n // 2) - 1\r\n",
    "        return f(n)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
